package class18_recursive;

import java.util.ArrayList;
import java.util.List;

class Board{
    public boolean[][] b;
    public int num;

    public Board(int n){
        b = new boolean[n][n];
        num=0;
    }

    public Board(Board board){
        int n = board.b.length;
        b = new boolean[n][n];
        for(int i=0;i<n;i++){
            for(int j=0; j<n; j++) {
                this.b[i][j] = board.b[i][j];
            }
        }
        num = board.num;
    }

    public void  putChess(int y, int x){
        if(!b[y][x]){
            b[y][x]=true;
            num++;
        }
    }

    public boolean isFull(){
        return num==b.length*b.length;
    }

    public void setNotValid(int y, int x){
        int n = b.length;
        for(int i = 0; i<n;i++){
            for(int j=0; j<n; j++){
                if(i==y || j==x || i-y == j-x || i+j == y+x){
                    putChess(i,j);
                }
            }
        }
    }

    public int firstValidRowIndex(int y){
        for(int i=0; i<b.length; i++){
            if(!b[y][i]) return i;
        }

        return -1;
    }
}

class Solution {

    public static String putQueen(int x,int n){//在一个行上方一个Q
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<n;i++){
            if(i==x) sb.append('Q');
            else sb.append('.');
        }
        return sb.toString();
    }

    public static  List<List<String>> solveNQueens(int n) {
        ArrayList<List<String>> ans = new ArrayList<>();
        ArrayList<String> cur = new ArrayList<>();
        Board board = new Board(n);
        process(n,0,board,ans,cur);
        return ans;
    }

    public static void process(int n, int y, Board board_, ArrayList<List<String>> ans, ArrayList<String> cur_){
        if(board_.isFull()) return;

        int fvr = board_.firstValidRowIndex(y);
        if(fvr!=-1){//这一行有得填
            ArrayList<String> cur = (ArrayList<String>)cur_.clone();
            if(y==n-1){//已经来到最后一行
                cur.add(putQueen(fvr,n));
                ans.add(cur);
            }
            else{
                for(int i=fvr;i<n;i++){
                    Board board = new Board(board_);
                    if(!board_.b[y][i]){//可以放皇后
                        board.setNotValid(y,i);
                        cur.add(putQueen(i,n));
                        process(n,y+1,board,ans,cur);
                        cur.remove(cur.size()-1);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        solveNQueens(4);
        ArrayList<Integer> a = new ArrayList<>();
        a.hashCode();
    }
}
